package leetcode;

/*
486. 预测赢家
给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。
给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。
示例 1：
输入：[1, 5, 2]
输出：False
解释：一开始，玩家1可以从1和2中进行选择。
如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。
所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。
因此，玩家 1 永远不会成为赢家，返回 False 。
示例 2：
输入：[1, 5, 233, 7]
输出：True
解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
     最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 True，表示玩家 1 可以成为赢家。
提示：
1 <= 给定的数组长度 <= 20.
数组里所有分数都为非负数且不会大于 10000000 。
如果最终两个玩家的分数相等，那么玩家 1 仍为赢家。
*/

public class problems_486 {
    public static void main(String[] arge) {
        System.out.println(new Solution().PredictTheWinner(new int[]{1, 5, 2, 4, 6}));
    }


//    static class Solution {
//        // 动态规划的方法
//        public boolean PredictTheWinner(int[] nums) {
//            // 由于有2个玩家，所以使用二维数组，dp[i][j]
//            // 每个格子标识可能的结果，为玩家1和玩家2都最大的结果
//            // 而i和j，则标识nums的下标，左右索引
//            // 因此i>j的情况，不合理，则不存在
//            int dp[][] = new int[nums.length][nums.length];
//
//
//
//
//        }
//    }

    static class Solution {
        // 递归的方法
        public boolean PredictTheWinner(int[] nums) {
            int ret = 0; // 使用ret作为结果，为玩家1-玩家2的分数
            return dfs(nums, 0, nums.length - 1, 1) >= 0;
        }

        // 递归计算用
        // mark是1和-1，标识玩家1和玩家2选择的结果影响
        private int dfs(int[] nums, int left, int right, int mark) {
            // 指针合并时，直接返回
            if (left == right) {
                return mark * nums[left]; // 返回当前结果
            }
            // 选择左侧
            int leftNum = mark * nums[left] + dfs(nums, left + 1, right, -mark);
            // 选择右侧
            int rightNum = mark * nums[right] + dfs(nums, left, right - 1, -mark);
            // 返回结果
            return mark * Math.max(mark * leftNum, mark * rightNum);
        }
    }

//    // 以下错误
//    static class Solution {
//        public boolean PredictTheWinner(int[] nums) {
//            Deque<Integer> deque = new ArrayDeque<>(nums.length); // 双向链表
//            for (int num : nums) deque.offer(num);
//            // 游戏者
//            Stack<Integer> play1 = new Stack<>();
//            Stack<Integer> play2 = new Stack<>();
//            if (dfs(deque, play1, play2, true)){
//                return true;
//            }else {
//                return false;
//            }
//        }
//        //
//        private boolean dfs(Deque<Integer> deque, Stack<Integer> play1, Stack<Integer> play2, boolean isPlay1 ){
//            System.out.print(deque);
//            System.out.print(play1);
//            System.out.print(play2);
//            System.out.println();
//            if (deque.isEmpty()){
//                return play1.stream().mapToInt(Integer::valueOf).sum() >= play2.stream().mapToInt(Integer::valueOf).sum();
//            }
//            // 判断使用哪个
//            boolean isFirst = deque.peekFirst() >= deque.peekLast();
//            Stack<Integer> play = isPlay1 ? play1 : play2;
//            // 使用对象
//            if (isFirst){
//                // 首
//                play.push(deque.pollFirst());
//                if (dfs(deque, play1, play2, !isPlay1)) return true;
//                deque.addFirst(play.pop());
//            }else {
//                // 尾
//                play.push(deque.pollLast());
//                if (dfs(deque, play1, play2, !isPlay1)) return true;
//                deque.addLast(play.pop());
//            }
//            return false;
//        }
//    }
}